Claire Mathieu, Brown University, Ecole Normale Superieure
We study the problem of reconstructing a hidden graph G given access to a distance oracle, when G can only be accessed by querying pairs of vertices and getting their shortest path distance in G. We wish to design randomized algorithms with small query complexity. We also study approximate reconstruction. Further, we explore the verification problem, in which we are given a mental picture of some unknown graph and wish to verify that our mental image is correct with few queries. We make progress on those problems for graphs of bounded degree, outerplanar graphs, and graphs of bounded tree width. (Joint work with Hang Zhou and Sampath Kannan)